package org.example.myleet.p650;

public class Solution {
    /**
     * 思路：分解质因数
     * 观察当n为质数时，所需操作次数 = (复制全部 + (n-1) * 粘贴) = n
     * 即n为质数时最少操作次数就是n
     */
    public int minSteps(int n) {
        if (n == 1) {
            return 0;
        }
        return process(n);
    }

    /**
     * 递归处理n，求得到n所需要的最少操作次数
     */
    private int process(int n) {
        //找最小因子
        int factor = findFactor(n);
        if (-1 == factor) {
            //找不到最小因子，说明是质数，操作次数等于n
            return n;
        }
        //找到最小因子factor，下一个递归目标是n / factor，并加上factor次操作即可得到n的最少操作次数
        return process(n / factor) + factor;
    }

    /**
     * 找到n的其中一个最小的因子，跟判断质数的原理差不多
     */
    private int findFactor(int n) {
        if (n < 4) {
            return -1;
        }
        int end = n / 2 + 1;
        for (int i = 2; i < end; ++i) {
            if (n % i == 0) {
                return i;
            }
        }
        return -1;
    }
}
